// Tags: GCD
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 1e6 + 5, inf = 0x3f3f3f3f;
int n, a[N], cnt[N], min[N][2], pri[N], tot, val, ans;
bool vis[N];

/**
 * @param d: value
 * @param x: index
 */
void update(int d, int x) {
  if (cnt[a[x]] < cnt[a[min[d][0]]]) min[d][1] = min[d][0], min[d][0] = x;
  else if (cnt[a[x]] < cnt[a[min[d][1]]] && x != min[d][0])
    min[d][1] = x;
}

/**
 * @param d value
 * @param x index
 */
void solve(int d, int x) {
  int y = min[d][0] == x ? min[d][1] : min[d][0],
      v = cnt[a[x]] + cnt[a[y]] - 2 * cnt[d];
  if (v < val || (v == val && y < ans)) val = v, ans = y;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P3532 [POI2012]ODL-Distance.in", "r", stdin);
  freopen("P3532 [POI2012]ODL-Distance.out", "w", stdout);
#endif
#endif

  read(n);
  for (int i = 2; i < N; ++i) {
    if (!vis[i]) pri[++tot] = i, cnt[i] = 1;
    for (int j = 1; j <= tot && pri[j] * i < N; ++j) {
      vis[i * pri[j]] = true;
      cnt[i * pri[j]] = cnt[i] + 1;
      if (i % pri[j] == 0) break;
    }
  }
  cnt[0] = inf;
  for (int i = 1; i <= n; ++i) {
    read(a[i]);
    for (int j = 1; j * j <= a[i]; ++j) {
      if (a[i] % j == 0) update(j, i), update(a[i] / j, i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    val = inf;
    for (int j = 1; j * j <= a[i]; ++j) {  // div
      if (a[i] % j == 0) solve(j, i), solve(a[i] / j, i);
    }
    printf("%d\n", ans);
  }
  return 0;
}